package com.leetcode.sorts.back_track;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: WuPeng
 * @Date: 2021/6/16 4:12 下午
 *
 * 93.复原IP地址
 * 给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。
 * 你可以按任何顺序返回答案。
 * 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
 * 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
 * 示例 1：
 *      输入：s = "25525511135"
 *      输出：["255.255.11.135","255.255.111.35"]
 * 示例 2：
 *      输入：s = "0000"
 *      输出：["0.0.0.0"]
 * 示例 3：
 *      输入：s = "1111"
 *      输出：["1.1.1.1"]
 * 示例 4：
 *      输入：s = "010010"
 *      输出：["0.10.0.10","0.100.1.0"]
 * 示例 5：
 *      输入：s = "101023"
 *      输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
 *
 */
public class RestoreIP_93 {
    private List<String> res = new ArrayList<>();
    private List<String> path = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        backTracking(s, 0);
        return res;
    }

    private void backTracking(String s, int index) {
        if (path.size() > 4){
            return;
        }
        if (path.size() == 4 && index != s.length()){
            return;
        }
        if (path.size() == 4){
            res.add(String.join(".", path));
            return;
        }
        for (int i = index; i < s.length(); i++) {
            String str = s.substring(index, i + 1);
            if ((str.length() > 1 && str.startsWith("0")) || str.length()>3) continue;
            int value = Integer.valueOf(str);
            if (value < 0 || value > 255) continue;
            path.add(str);
            backTracking(s, i+1);
            path.remove(path.size()-1);
        }
    }

    public static void main(String[] args) {
        String s = "25525511135";
        RestoreIP_93 restoreIp = new RestoreIP_93();
        List<String> list = restoreIp.restoreIpAddresses(s);
        System.out.println(Arrays.toString(list.toArray()));
    }

}
